package org.java.tree.rbtree;

public class RB_Tree {
	final Boolean RED = false;
	final Boolean BLACK = true;
	Node root;
	Node nil;

	public RB_Tree() {
		nil = new Node();
		nil.color = BLACK;
		root = nil;

	}

	public class Node {
		int key;
		Node p;
		Node left;
		Node right;
		Boolean color;

		public Node() {
		}

		public Node(int key) {
			this.key = key;
		}

		public Node(int key, Node left, Node right) {
			this.key = key;
			this.p = null;
			this.left = left;
			this.right = right;
			this.color = RED;
		}

		public Node(int key, Node p, Node left, Node right, Boolean color) {
			this.key = key;
			this.p = p;
			this.left = left;
			this.right = right;
			this.color = color;
		}
	}

	// Function to create node of the tree.
	public Node createNode() {
		Node node = new Node();
		return node;
	}

	public Node createNode(int key) {
		Node node = new Node(key);
		return node;
	}

	public Node createNode(int key, Node left, Node right) {
		Node node = new Node(key, left, right);
		return node;
	}

	public Node createNode(int key, Node p, Node left, Node right, Boolean color) {
		Node node = new Node(key, p, left, right, color);
		return node;
	}

	// Function of rotation.
	public void LEFT_ROTATE(RB_Tree T, Node x) {
		Node y = x.right;
		x.right = y.left;
		if (y.left != T.nil) {
			y.left.p = x;
		}
		y.p = x.p;
		if (x.p == T.nil) {
			T.root = y;
		} else {
			if (x == x.p.left) {
				x.p.left = y;
			} else {
				x.p.right = y;
			}
		}
		y.left = x;
		x.p = y;
	}

	public void RIGHT_ROTATE(RB_Tree T, Node x) {
		Node y = x.left;
		x.left = y.right;
		if (y.right != nil) {
			y.right.p = x;
		}
		y.p = x.p;
		if (x.p == T.nil) {
			T.root = y;
		} else {
			if (x == x.p.right) {
				x.p.right = y;
			} else {
				x.p.left = y;
			}
		}
		y.right = x;
		x.p = y;
	}

	// Function of successor.
	public Node TREE_MINIMUM(RB_Tree T, Node x) {
		while (x.left != T.nil) {
			x = x.left;
		}
		return x;
	}

	public Node TREE_MAXIMUM(RB_Tree T, Node x) {
		while (x.right != T.nil) {
			x = x.right;
		}
		return x;
	}

	public Node TREE_SUCCESSOR(RB_Tree T, Node x) {
		if (x.right != T.nil) {
			return TREE_MINIMUM(T, x.right);
		}
		Node y = x.p;
		while (y != T.nil && x == y.right) {
			x = y;
			y = y.p;
		}
		return y;
	}

	public Node TREE_PREDECESSOR(RB_Tree T, Node x) {
		if (x.left != T.nil) {
			return TREE_MAXIMUM(T, x.left);
		}
		Node y = x.p;
		while (y != T.nil && x == y.left) {
			x = y;
			y = y.p;
		}
		return y;
	}

	// Function of insert.
	public void RB_INSERT(RB_Tree T, Node z) {
		Node y = T.nil;
		Node x = T.root;
		while (x != T.nil) {
			y = x;
			if (z.key < x.key) {
				x = x.left;
			} else {
				x = x.right;
			}
		}
		z.p = y;
		if (y == T.nil) {
			T.root = z;
		} else {
			if (z.key < y.key) {
				y.left = z;
			} else {
				y.right = z;
			}
		}
		z.left = T.nil;
		z.right = T.nil;
		z.color = RED;
		RB_INSERT_FIXUP(T, z);
	}

	public void RB_INSERT_FIXUP(RB_Tree T, Node z) {
		Node y;
		while (z.p.color == RED) {
			if (z.p == z.p.p.left) {
				y = z.p.p.right;
				if (y.color == RED) {
					z.p.color = BLACK;
					y.color = BLACK;
					z.p.p.color = RED;
					z = z.p.p;
				} else {
					if (z == z.p.right) {
						z = z.p;
						LEFT_ROTATE(T, z);
					}
					z.p.color = BLACK;
					z.p.p.color = RED;
					RIGHT_ROTATE(T, z.p.p);
				}
			} else {
				y = z.p.p.left;
				if (y.color == RED) {
					z.p.color = BLACK;
					y.color = BLACK;
					z.p.p.color = RED;
					z = z.p.p;
				} else {
					if (z == z.p.left) {
						z = z.p;
						RIGHT_ROTATE(T, z);
					}
					z.p.color = BLACK;
					z.p.p.color = RED;
					LEFT_ROTATE(T, z.p.p);
				}
			}
		}
		T.root.color = BLACK;
	}

	// Function of search.
	public Node RB_SEARCH_RECURSION(Node x, int key) {
		if (x == nil || key == x.key) {
			return x;
		}
		if (key < x.key) {
			return RB_SEARCH_RECURSION(x.left, key);
		} else {
			return RB_SEARCH_RECURSION(x.right, key);
		}
	}

	public Node RB_SEARCH_ITERATIVE(Node x, int key) {
		if (x == nil || key == x.key) {
			return x;
		}
		while (key != x.key) {
			if (key < x.key) {
				x = x.left;
			} else {
				x = x.right;
			}
		}
		return x;
	}

	// Function of delete.
	public Node RB_DELETE(RB_Tree T, Node z) {
		Node y;
		Node x;
		if (z.left == T.nil || z.right == T.nil) {
			y = z;
		} else {
			y = TREE_SUCCESSOR(T, z);
		}
		if (y.left != T.nil) {
			x = y.left;
		} else {
			x = y.right;
		}
		x.p = y.p;
		if (y.p == T.nil) {
			T.root = x;
		} else {
			if (y == y.p.left) {
				y.p.left = x;
			} else {
				y.p.right = x;
			}
		}
		if (y != z) {
			z.key = y.key;
			// Copy y's satellite data into z.
		}
		if (y.color == BLACK) {
			RB_DELETE_FIXUP(T, x);
		}
		return y;
	}

	public void RB_DELETE_FIXUP(RB_Tree T, Node x) {
		Node w;
		while (x != T.root && x.color == BLACK) {
			if (x == x.p.left) {
				w = x.p.right;
				if (w.color == RED) {
					w.color = BLACK;
					x.p.color = RED;
					LEFT_ROTATE(T, x.p);
					w = x.p.right;
				}
				if (w.left.color == BLACK && w.right.color == BLACK) {
					w.color = RED;
					x = x.p;
				} else {
					if (w.right.color == BLACK) {
						w.left.color = BLACK;
						w.color = RED;
						RIGHT_ROTATE(T, w);
						w = x.p.right;
					}
					w.color = x.p.color;
					x.p.color = BLACK;
					w.right.color = BLACK;
					LEFT_ROTATE(T, x.p);
					x = T.root;
				}
			} else {
				w = x.p.left;
				if (w.color == RED) {
					w.color = BLACK;
					x.p.color = RED;
					RIGHT_ROTATE(T, x.p);
					w = x.p.left;
				}
				if (w.right.color == BLACK && w.left.color == BLACK) {
					w.color = RED;
					x = x.p;
				} else {
					if (w.left.color == BLACK) {
						w.right.color = BLACK;
						w.color = RED;
						LEFT_ROTATE(T, w);
						w = x.p.left;
					}
					w.color = x.p.color;
					x.p.color = BLACK;
					w.left.color = BLACK;
					RIGHT_ROTATE(T, x.p);
					x = T.root;
				}
			}
		}
		x.color = BLACK;
	}

}
